//邻接矩阵基本操作+深度广度优先遍历
//**************************引入头文件*****************************
#include <stdio.h>   //使用了标准库函数 
#include <stdlib.h>  //使用了动态内存分配函数
#include <windows.h>
#include "my_constants.h" //引入自定义的符号常量，主要是状态码 
#include "SqQueue.cpp"    //由于广度优先遍历要使用队列，插入删除少访问多，故引入顺序队列 
#include "MGraph.h"       //引入图的邻接矩阵表示法的基本定义 
#include "MGraph.cpp"     //引入图的主要操作
#include "DFS_BFS_Traverse_MGraph.cpp" //引入图的深度优先和广度优先遍历算法实现 


//----------------------主函数----------------------
int main(int argc, char *argv[]){
  system("chcp 65001 > nul");
	printf("\n-------------图的邻接矩阵表示法基本操作测试程序--------------\n\n"); 
	
	//图G 
	MGraph G; 
	
	//临时变量，保存输入的顶点 
	VertexType v1, v2;
	
	//临时变量，保存输入的顶点数 
	int n;
	
	//图的创建
	printf("->测试图的创建：\n");
	CreateGraph(G);
	
	//打印邻接矩阵
	printf("\n->创建成功后图的邻接矩阵:\n\n"); 
	PrintAdjMatrix(G);
	
	//测试图的遍历（深度、广度） 
	printf("\n->测试图的遍历:\n");
	printf("->深度优先遍历结果：");
	DFSTraverse(G, Print);
	
	printf("\n->广度优先遍历结果：");
	BFSTraverse(G, Print);
	printf("\n");
	
	//测试插入顶点和边的操作 
	printf("\n->测试插入新顶点\n ");
	printf("->请输入顶点的值: ");
    scanf("%d", &v1);
    InsertVex(G, v1);
    
    printf("->测试插入边\n");
	printf("->插入与新顶点（有向图或网中的弧尾）有关的弧或边，请输入弧或边数: ");
    scanf("%d", &n);
    for(int k = 0; k < n; k++) {
    	
    	printf("->请输入另一顶点（弧头）的值: ");
    	scanf("%d", &v2);
        
        //以v1为弧尾,v2为弧头插入弧 
		InsertArc(G, v1, v2);
    }
    
    printf("->插入顶点和弧后图的邻接矩阵:\n\n"); 
    PrintAdjMatrix(G);
    
    //测试删除顶点 
    printf("\n->删除顶点及相关的弧或边，请输入顶点的值: ");
    scanf("%d", &v1);
    DeleteVex(G, v1);
    
    printf("->删除顶点和弧后图的邻接矩阵:\n\n"); 
    PrintAdjMatrix(G);
    
    //测试销毁 
    printf("\n->测试销毁图： ");
	DestroyGraph(G); 
	printf("成功！\n");
	
	printf("演示结束，程序退出！\n");
	
	return 0;
} 

/*--------------------------输入全程记录（便于测试，可直接复制）------------------------------ 

   说明：下面输入的无向图来自教材P174页


-------------图的邻接矩阵表示法基本操作测试程序--------------

->测试图的创建：
请输入您想构造的图的类型:有向图输入0,有向网输入1,无向图输入2,无向网输入3):3
请依次输入无向网G的顶点数，弧数，用逗号隔开
6,10
请依次输入无向网G的顶点名称，用空格隔开
1 2 3 4 5 6
请依次输入无向网G每条弧依附的两顶点名称及权值，输完一组按回车
1 2 6
1 4 5
1 3 1
3 2 5
3 4 5
3 5 6
3 6 4
2 5 3
4 6 2
5 6 6

->创建成功后图的邻接矩阵:

         1    2    3    4    5    6
     +------------------------------
   1 |  ∞    6    1    5   ∞   ∞
     |
   2 |   6   ∞    5   ∞    3   ∞
     |
   3 |   1    5   ∞    5    6    4
     |
   4 |   5   ∞    5   ∞   ∞    2
     |
   5 |  ∞    3    6   ∞   ∞    6
     |
   6 |  ∞   ∞    4    2    6   ∞
     |

->测试图的遍历:
->深度优先遍历结果：   1    2    3    4    6    5
->广度优先遍历结果：   1    2    3    4    5    6

->测试插入新顶点
->请输入顶点的值: 7

->测试插入边
 ->插入与新顶点（有向图或网中的弧尾）有关的弧或边，请输入弧或边数: 2
->请输入另一顶点（弧头）的值: 2
请输入此弧或边的权值: 10
->请输入另一顶点（弧头）的值: 5
请输入此弧或边的权值: 15
->插入顶点和弧后图的邻接矩阵:

         1    2    3    4    5    6    7
     +-----------------------------------
   1 |  ∞    6    1    5   ∞   ∞   ∞
     |
   2 |   6   ∞    5   ∞    3   ∞   10
     |
   3 |   1    5   ∞    5    6    4   ∞
     |
   4 |   5   ∞    5   ∞   ∞    2   ∞
     |
   5 |  ∞    3    6   ∞   ∞    6   15
     |
   6 |  ∞   ∞    4    2    6   ∞   ∞
     |
   7 |  ∞   10   ∞   ∞   15   ∞   ∞
     |

->删除顶点及相关的弧或边，请输入顶点的值: 7
->删除顶点和弧后图的邻接矩阵:

         1    2    3    4    5    6
     +------------------------------
   1 |  ∞    6    1    5   ∞   ∞
     |
   2 |   6   ∞    5   ∞    3   ∞
     |
   3 |   1    5   ∞    5    6    4
     |
   4 |   5   ∞    5   ∞   ∞    2
     |
   5 |  ∞    3    6   ∞   ∞    6
     |
   6 |  ∞   ∞    4    2    6   ∞
     |

->测试销毁图： 成功！
演示结束，程序退出！

--------------------------------
Process exited with return value 0
Press any key to continue . . .


*/
